package HW3;




public class Test {
	
	
	public static int inversion(int []inputs)
	{
		int[] sortedA = mergeSort(inputs);
		return 0;
	//add your code for Q1 here
	}

	public static boolean isBinarySearchTree(TreeNode root)
	{
		return false;
	//add your code for Q2 here.

	}
	public static int maxSum(TreeNode root)
	{
		return 0;
	//add your code for Q3 here.
		
	}
	
	public static int[] mergeSort(int[]a)
	{
		int[] sorted = new int[a.length];
		if(a.length == 1){
			return a;
		}else if(a.length == 2)
		{  
			int[] temp = new int[2];
			if(a[0] > a[1])
			{
				temp[0] = a[1];
				temp[1] = a[0];
			}else
			{
				temp[0] = a[0];
				temp[1] = a[1];
			}
			return temp;
			
		}else{
			//int[] a1 = new int[a.length/2];
			//int[] a2 = new int[a.length -(a.length/2)];

			//System.arraycopy(src, 1, dst, 0, 3); // Copies 2, 3, 4 into dst
			int[] a1 = java.util.Arrays.copyOfRange(a, 0, a.length/2);
			int[] a2 = java.util.Arrays.copyOfRange(a, a.length/2 , a.length);
			int[] b1 = new int[a1.length];
			int[] b2 = new int[a2.length];
			b1 = mergeSort(a1);
			b2 = mergeSort(a2);
			sorted = merge(b1,b2);
			
			return sorted;
			
		}
		
	}

	private static int[] merge(int[] a1, int[] a2) {
		
		int j = 0;
		int k = 0;
		int[] comb = new int[a1.length + a2.length];
	
		for(int i = 0; i < (a1.length + a2.length); i++)
		{
			if(j == a1.length)
			{
				j--;
				//Place infinity (could have used a sentinel value)
				a1[j] = 1999999999;
			}
			if(k == a2.length)
			{
				k--;
				//Place infinity (could have used sentinel value)
				a2[k] = 1999999999;
			}
			if(a1[j] < a2[k])
			{
				comb[i] = a1[j];
				j++;
			}else
			{
				comb[i] = a2[k];
				k++;
			}
		}
		// TODO Auto-generated method stub
		return comb;
	}
	

	
	public static void main(String args[])
	{
	  int[] myinput = {13, 7, 4, 11, 43, 10, 2};
	  int num_of_inversion = Test.inversion(myinput);
	  System.out.println("Uncomment code to run the test or create your on test"); 		
	}

}
